Trip routing problems present the question how to travel from a first location to a second location efficiently. Often, additional constraints may be present. For example, the trip must be completed within a certain period of time, or must pass through certain intermediate waypoints. The general form of many trip routing problems is called “NP Complete,” signifying that the problem is of a class that cannot be solved in polynomial time by any known algorithm, and furthermore that the problem is equivalent to other problems in the class, so that an algorithm to solve one problem could be applied to solve the others as well.
Although there is currently no known solution to the general trip routing problem, heuristics have been identified that often lead to an acceptable (if not provably optimal) solution within a reasonable amount of time. Because routing problems appear in many business situations, new heuristics to help find, refine and evaluate practical solutions can be of great value.
One factor that affects practical trip routing is legal restrictions imposed by countries, cities, or other political subdivisions upon vehicles carrying cargo through their jurisdiction. Another factor is physical restrictions such as height, width and weight limitations. Current routing heuristics often cannot model such restrictions correctly, and may not be able to evaluate trips dynamically. A heuristic that can deal with legal, physical, and similar restrictions, and do so for trips between arbitrary locations and at arbitrary times, may be useful.